---
title: "走迷宫"
created: 2025-11-28
tags:
  - 算法
---

# 走迷宫

## 题目 [走迷宫](https://www.acwing.com/problem/content/846/)

![[image-bf293d39.png]]

## 思路分析

逻辑与dfs差不多 都是可以先默写上 dx，dy 以及isVaild

拓展也是4个方向 不过得先存在队列里面 先进先出的方式处理

另外不同的是 用一个d数组代替st数组 现在要记录每个点距离起点的距离 也可以等效地用来判断某个点用没用过 并多维护了一些信息

## 代码实现

```cpp
 #include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=110;

int g[N][N],d[N][N];

int n,m;

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

bool isVaild(int x,int y){

	return x>=1 && x<=n && y>=1 && y<=m && d[x][y]==-1;

}

int bfs(int x,int y){

	queue<PII> q;

	memset(d,-1,sizeof d);

	d[x][y]=0;

	q.push({x,y});

	while(!q.empty()){

		auto cur=q.front();

		int ux=cur.first,uy=cur.second;

		q.pop();

		for(int i=0;i<4;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny) && g[nx][ny]==0){

				d[nx][ny]=d[ux][uy]+1;

				q.push({nx,ny});

			}

		}

	}

	return d[n][m];

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			cin>>g[i][j];

		}

	}

	cout<<bfs(1,1);

	return 0;

 }
```

## 同类题型

## 视频讲解

---
⬅️ [[离开中山路|离开中山路]] 🏠 [[00-刷题理模型]] ➡️ [[迷宫问题|迷宫问题]]